def lcs(A, B):
    m = len(A)
    n = len(B)

    assert(m <= n)

    M = [-1] * (m+1) # M is (m+1) * (m+1)
    for i in range(len(M)):
        M[i] = [-1] * (m+1)
    
    diagonal_pos = m - 1
    length_MAX = 0
    pos_A = 0
    upper_B = 0

    # Calculate M(i, j)
    while length_MAX < diagonal_pos:
        pos_A = diagonal_pos
        length_LCS = 0
        upper_B = n

        # Calculate M(i, j) on one diagonal
        while pos_A != -1 and upper_B != -1:
            if diagonal_pos == m-1 or length_LCS > length_MAX:
                M[length_LCS][pos_A + 1] = -1

            lower_B = max(0, M[length_LCS][pos_A + 1])
            pos_B = upper_B - 1

            # Calculate one M(i, j) according to Lemma 3
            while pos_B >= lower_B and A[pos_A] != B[pos_B]:
                pos_B = pos_B - 1

            if pos_B >= lower_B:
                upper_B = pos_B
            else:
                upper_B = M[length_LCS][pos_A + 1]

            M[length_LCS][pos_A] = upper_B

            if upper_B == -1:
                length_LCS = length_LCS - 1

            length_MAX = max(length_MAX, length_LCS)
            length_LCS = length_LCS + 1
            pos_A = pos_A - 1

        diagonal_pos = diagonal_pos - 1

    LCS_A = [-1] * (m+1)
    LCS_B = [-1] * (m+1)

    # Recover LCS
    if upper_B == -1:
        pos_A = pos_A + 2
    else:
        pos_A = pos_A + 1

    pos_LCS = length_MAX

    while pos_LCS > -1:
        while M[pos_LCS][pos_A] == M[pos_LCS][pos_A + 1]:
            pos_A = pos_A + 1
        
        LCS_A[pos_LCS] = pos_A
        LCS_B[pos_LCS] = M[pos_LCS][pos_A]
        pos_A = pos_A + 1
        pos_LCS = pos_LCS - 1

    lcs_a = ''
    lcs_b = ''

    for i in range(len(LCS_A))[::-1]:
        if LCS_A[i] != -1:
            lcs_a += A[LCS_A[i]]

    for i in range(len(LCS_B))[::-1]:
        if LCS_B[i] != -1:
            lcs_b += B[LCS_B[i]]
            
    print 'Equal?', lcs_a == lcs_b
    return lcs_a

print lcs('GTCGTTCGGAATGCCGTTGCTCTGTAAA', 'ACCGGTCGAGTGCGCGGAAGCCGGCCGAA')
print lcs('bcdabab', 'cbacbaaba')
